DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2022.66

Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions

Authors: Meryem Essaidi, Matheus V. X. Ferreira, and S. Matthew Weinberg

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract

We consider a revenue-maximizing seller with a single item for sale to multiple buyers with independent and identically distributed valuations. Akbarpour and Li (2020) show that the only optimal, credible, strategyproof auction is the ascending price auction with reserves which has unbounded communication complexity. Recent work of Ferreira and Weinberg (2020) circumvents their impossibility result assuming the existence of cryptographically secure commitment schemes, and designs a two-round credible, strategyproof, optimal auction. However, their auction is only credible when buyers' valuations are MHR or α-strongly regular: they show their auction might not be credible even when there is a single buyer drawn from a non-MHR distribution. In this work, under the same cryptographic assumptions, we identify a new single-item auction that is credible, strategyproof, revenue optimal, and terminates in constant rounds in expectation for all distributions with finite monopoly price.

Cite as

Meryem Essaidi, Matheus V. X. Ferreira, and S. Matthew Weinberg. Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 66:1-66:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{essaidi_et_al:LIPIcs.ITCS.2022.66,
  author =	{Essaidi, Meryem and Ferreira, Matheus V. X. and Weinberg, S. Matthew},
  title =	{{Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{66:1--66:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.66},
  URN =		{urn:nbn:de:0030-drops-156621},
  doi =		{10.4230/LIPIcs.ITCS.2022.66},
  annote =	{Keywords: Credible Auctions, Cryptographically Secure, Single-Item}
}

Search Results

Documents authored by Essaidi, Meryem

Credible, Strategyproof, Optimal, and Bounded Expected-Round Single-Item Auctions for All Distributions

Abstract

Cite as

Thanks for your feedback!

Could not send message